// Copyright (C) 2019 Alibaba Group Holding Limited
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//    http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// ===========================================================================
//
// This impaseentation is heavily influenced by the NMSlib and Faiss.
// https://github.com/searchivarius/nmslib
// https://github.com/facebookresearch/faiss.git

// 版权所有 (C) 2019 阿里巴巴集团控股有限公司
//
// 根据 Apache 许可证，版本 2.0（"许可证"）进行许可；
// 除非符合许可证的规定，否则您不能使用此文件。
// 您可以在以下网址获取许可证副本：
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// 除非适用法律要求或书面同意，否则在 "按原样" 的基础上分发本软件，
// 没有任何明示或暗示的保证或条件。
// 有关特定语言的详细信息，请参阅许可证。
// ===========================================================================
//
// 此实现受到 NMSlib 和 Faiss 的强烈影响。
// https://github.com/searchivarius/nmslib
// https://github.com/facebookresearch/faiss.git


#ifndef PASE_HNSW_HNSW_H_
#define PASE_HNSW_HNSW_H_
/*
这些库头文件是从 PostgreSQL 数据库源代码中引用的，
它们用于开发 PostgreSQL 扩展模块或进行数据库访问、管理等操作。
每个头文件提供了一组函数、宏和数据结构，允许您与 PostgreSQL 
数据库系统进行交互。以下是这些头文件的简要描述和来自的源路径：

access/amapi.h: 提供了索引方法（access method）相关的接口和函数。来自路径 src/include/access/amapi.h。
access/generic_xlog.h: 用于通用事务日志（xlog）管理的接口和函数。来自路径 src/include/access/generic_xlog.h。
access/itup.h: 提供了关于索引元组（index tuple）的操作和数据结构定义。来自路径 src/include/access/itup.h。
access/xlog.h: 提供了事务日志（xlog）管理的接口和函数。来自路径 src/include/access/xlog.h。
fmgr.h: 提供了 PostgreSQL 函数管理器（function manager）的接口，用于定义和管理用户自定义函数。来自路径 src/include/fmgr.h。
lib/pairingheap.h: 提供了二叉堆（binary heap）数据结构的实现，用于高效地管理一组数据。来自路径 src/include/lib/pairingheap.h。
nodes/relation.h: 定义了与数据库关系（relation）和表格（table）相关的数据结构和操作。来自路径 src/include/nodes/relation.h。

*/
#include "access/amapi.h"
#include "access/generic_xlog.h"
#include "access/itup.h"
#include "access/xlog.h"
#include "fmgr.h"
#include "lib/pairingheap.h"
#include "nodes/relation.h"

#include "utils/pase_hash_table.h"
#include "utils/pase_page_list.h"
#include "utils/priority_queue.h"
#include "type/pase_data.h"

#define MAX_HNSW_LEVEL 100
#define HNSW_METAPAGE_BLKNO 0
#define HNSW_MAGICK_NUMBER (0xDBAC0EEE)            // 识别是否为HNSW索引的关键值

typedef struct HNSWGlobalId {
  int32 nblkid;   // 一个块的id
  int32 dblkid;   // 另一个块的id
  int32 doffset;  // 偏移值
} HNSWGlobalId;

typedef struct HNSWOptions {
  int32 vl_len_;                                        // 存储结构体的长度信息
  int32 dim;                                            // 数据的维度
  int32 base_nb_num;                                    // 每个节点的基本邻居数。
  int32 real_max_level;                                 // 实际的最大层级数
  int32 ef_build;                                       // 构建索引时的探索因子
  int32 ef_search;                                      // 搜索时的探索因子
  int32 base64_encoded;                                 // 是否使用Base64编码
  uint16 nb_tup_size;                                   // 邻居元组的大小
  uint16 data_tup_size;                                 // 数据元组的大小
  // cumulative neighbor num on all lower level
  uint16 cum_nn_per_level[MAX_HNSW_LEVEL + 1];          // 存储每个层级的累积邻居数量
  float4 assign_probas[MAX_HNSW_LEVEL];                 // 存储每个层级的分配概率
} HNSWOptions;

typedef struct HNSWBuildState {
  HNSWOptions opts;                               // 存储HNSW索引的选项参数
  MemoryContext tmpctx;                           // 临时内存上下文，用于在构建索引过程中分配临时内存
  uint16 count;                                   // 当前已插入的数据项数量
  int32 pre_data_blkid;                           // 先前数据块的ID
  int32 data_entry_blkid;                         // 数据项块的ID
  int32 cur_max_level;                            // 当前的最大层级数
  HNSWGlobalId entry_gid;                         // 表示入口数据项的全局ID
  int64 indtuples;                                // 已插入的索引元组数量
  PGAlignedBlock data;                            // 表示对齐的数据块
} HNSWBuildState;

// 定义了HNSW数据页的不透明数据结构
typedef struct HNSWDataPageOpaqueData {
  int32 maxoff;            // 数据页中的最大偏移量
  int32 next_blkid;        // 下一个数据页的块ID
} HNSWDataPageOpaqueData;
typedef HNSWDataPageOpaqueData *HNSWDataPageOpaque;

// 定义了HNSW数据元组结构体
typedef struct HNSWDataTuple {
  PaseTuple tag;                         // PaseTupleList的标签
  ItemPointerData heap_ptr;              // 堆指针
  uint16 level;                          // 层级
  float4 vector[FLEXIBLE_ARRAY_MEMBER];  // 可变长度的向量数组
} HNSWDataTuple;

// 定义了HNSW优先队列节点结构体
typedef struct HNSWPriorityQueueNode {
  PriorityQueueNode pr_node;  // 用于优先队列的节点
  HNSWGlobalId gid;           // 全局ID
  double distance;            // 距离
} HNSWPriorityQueueNode;

// 定义了HNSW邻居页的不透明数据结构
typedef struct HNSWNeighborPageOpaqueData {
  int32 maxoff;               // 邻居页中的最大偏移量
  int32 next_blkid;           // 下一个邻居页的块ID
} HNSWNeighborPageOpaqueData;
typedef HNSWNeighborPageOpaqueData *HNSWNeighborPageOpaque;

// 定义了HNSW邻居元组结构体
typedef struct HNSWNeighborTuple {
  PaseTuple tag;              // PaseTupleList的标签
  HNSWGlobalId gid;           // 全局ID
} HNSWNeighborTuple;

// 定义了HNSW元页面的数据结构
typedef struct HNSWMetaPageData {
  uint32 magick_num;          // 魔数， 判断是否是hnsw
  HNSWGlobalId entry_gid;     // 入口数据项的全局ID
  // real data page blkid
  int32 last_data_blkid;      // 最后一个数据块的ID
  HNSWOptions opts;           // HNSW索引的选项参数
} HNSWMetaPageData;
typedef HNSWMetaPageData* HNSWMetaPage;

// 定义了HNSW扫描的不透明数据结构
typedef struct HNSWScanOpaqueData {
    PASE*  scan_pase;          // 扫描的PASE
    MemoryContext scan_ctx;    // 扫描的内存上下文
    PriorityQueue* queue;      // 优先队列
    uint16 data_tup_size;      // 数据元组的大小
    bool first_call;           // 是否是第一次调用
} HNSWScanOpaqueData;
typedef HNSWScanOpaqueData* HNSWScanOpaque;


// hnsw_build.c
// hnsw_build函数用于构建HNSW索引，接受堆表和索引表以及索引信息作为参数
extern IndexBuildResult *hnsw_build(Relation heap, Relation index,
    struct IndexInfo *indexInfo);

// hnsw_buildempty函数用于在索引表中创建一个空的HNSW索引
extern void hnsw_buildempty(Relation index);

// hnsw_costestimate函数用于估算HNSW索引的成本，接受查询规划器信息、索引路径、循环次数以及成本、选择性、相关性和页数等参数
extern void hnsw_costestimate(PlannerInfo *root, IndexPath *path,
     double loopCount, Cost *indexStartupCost,
     Cost *indexTotalCost, Selectivity *indexSelectivity,
     double *indexCorrelation, double *indexPages);

// hnsw_scan.c
// hnsw_beginscan函数用于开始一个HNSW索引的扫描，接受关系表和键的数量以及排序的数量作为参数
extern IndexScanDesc hnsw_beginscan(Relation r, int nkeys, int norderbys);

// hnsw_rescan函数用于重新扫描HNSW索引，接受扫描描述符、扫描键、扫描键的数量、排序键和排序键的数量作为参数
extern void hnsw_rescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
     ScanKey orderbys, int norderbys);

// hnsw_gettuple函数用于获取HNSW索引中的元组，接受扫描描述符和扫描方向作为参数
extern bool hnsw_gettuple(IndexScanDesc scan, ScanDirection dir);

// hnsw_endscan函数用于结束HNSW索引的扫描，接受扫描描述符作为参数
extern void hnsw_endscan(IndexScanDesc scan);

// hnsw_insert.c
// hnsw_insert函数用于向HNSW索引中插入元组，接受索引表、值、是否为空、堆表的位置、堆表、唯一性检查标志和索引信息作为参数
extern bool hnsw_insert(Relation index, Datum *values, bool *isnull,
     ItemPointer htCtid, Relation heapRel,
     IndexUniqueCheck checkUnique,
     struct IndexInfo *indexInfo);

// InitHNSWBuildState4Insert函数用于初始化插入操作的HNSW构建状态，接受元数据页和构建状态作为参数
extern void
InitHNSWBuildState4Insert(HNSWMetaPageData *meta, HNSWBuildState *state);

// HNSWFillMetaPage函数用于填充HNSW索引的元数据页，接受索引表和构建状态作为参数
extern void
HNSWFillMetaPage(Relation index, HNSWBuildState *state);


////////////////////////////////////////////////
// HNSWVtable gid wraper（HNSWVtable gid包装器）
typedef struct HNSWVtable {
  PaseHashTable *vt1;  // vt1哈希表指针
  PaseHashTable *vt2;  // vt2哈希表指针
} HNSWVtable;

extern void HVTInit(MemoryContext ctx, HNSWVtable *vt);  // 初始化HNSWVtable（内存上下文，HNSWVtable指针）
extern void HVTReset(HNSWVtable *vt);  // 重置HNSWVtable（HNSWVtable指针）
extern void HVTSet(HNSWVtable *vt, HNSWGlobalId gid);  // 设置HNSWVtable（HNSWVtable指针，全局ID）
extern bool HVTGet(HNSWVtable *vt, HNSWGlobalId gid);  // 获取HNSWVtable（HNSWVtable指针，全局ID）
extern void HVTFree(HNSWVtable *vt);  // 释放HNSWVtable（HNSWVtable指针）

////////////////////////////////////////////////

// data page macros
#define HNSWDATATUPLEHDRSZ offsetof(HNSWDataTuple, vector)
#define GetHNSWDataPageOpaque(_page)  \
  ((HNSWDataPageOpaque) PageGetSpecialPointer(_page))
#define HNSWDataPageGetMaxOffset(_page) (GetHNSWDataPageOpaque(_page)->maxoff)
#define HNSWDataPageGetFreeSpace(_state, _page)                      \
  (BLCKSZ - MAXALIGN(SizeOfPageHeaderData)                           \
    - HNSWDataPageGetMaxOffset(_page) * (_state)->opts.data_tup_size \
    - MAXALIGN(sizeof(HNSWDataPageOpaqueData)))
#define HNSWDataPageGetTuple(_data_tup_size, _page, _offset)  \
  ((HNSWDataTuple *)(PageGetContents(_page)                   \
    + (_data_tup_size) * ((_offset) - 1)))

// neighbor page macros
#define HNSW_GID(_gid, _nbid, _dtid, _offset)          \
  do {                                                 \
    (_gid).nblkid = _nbid;                             \
    (_gid).dblkid = _dtid;                             \
    (_gid).doffset = _offset;                          \
  } while (0)                                          \

#define HNSW_CHECK_GID(_gid)  ((_gid).nblkid <= 0 && (_gid).dblkid <= 0 && (_gid).doffset <= 0)

#define HNSW_CHECK_GID_EQ(_gid1, _gid2)      \
  ((_gid1).nblkid == (_gid2).nblkid && (_gid1).dblkid == (_gid2).dblkid && (_gid1).doffset == (_gid2).doffset)

#define GetHNSWNeighborPageOpaque(_page) \
  ((HNSWNeighborPageOpaque) PageGetSpecialPointer(_page))
#define HNSWNeighborPageGetMaxOffset(_page) \
  (GetHNSWNeighborPageOpaque(_page)->maxoff)

#define HNSWNeighborPageGetTuple(_state, _page, _offset) \
  ((HNSWNeighborTuple *)(PageGetContents(_page)          \
    + (_state)->opts.nb_tup_size * ((_offset) - 1)))

#define HNSWNeighborPageGetFreeSpace(_state, _page)                    \
  (BLCKSZ - MAXALIGN(SizeOfPageHeaderData)                             \
    - HNSWNeighborPageGetMaxOffset(_page) * (_state)->opts.nb_tup_size \
    - MAXALIGN(sizeof(HNSWNeighborPageOpaqueData)))

// init cache data or nb page
#define HNSW_INIT_CACHE_PAGE(_type, _state)                     \
  do {                                                          \
    _type opaque;                                               \
    memset((_state)->data.data, 0, BLCKSZ);                     \
    PageInit((_state)->data.data, BLCKSZ, sizeof(_type##Data)); \
    opaque = Get##_type((_state)->data.data);                   \
    memset(opaque, 0, sizeof(_type##Data));                     \
    opaque->next_blkid= (_state)->pre_data_blkid;               \
    (_state)->count = 0;                                        \
  } while (0)

#define ADD_HNSW_PQ_NODE(_queue, _gid, _distance)                            \
  do {                                                                       \
    HNSWPriorityQueueNode *node_xxx = palloc(sizeof(HNSWPriorityQueueNode)); \
    node_xxx->gid = (_gid);                                                  \
    node_xxx->distance = (_distance);                                        \
    PriorityQueueAdd(_queue, (PriorityQueueNode *)node_xxx);                 \
  } while (0)

// utils
int HNSWPriorityQueueCmp(const PriorityQueueNode *a,
    const PriorityQueueNode *b, void *arg);
// options
extern HNSWOptions *MakeDefaultHNSWOptions();
// flush cached page when it is full
extern int HNSWFlushCachedPage(Relation index, HNSWBuildState *buildState);
extern void HNSWInitMetapage(Relation index);
extern void InitHNSWBuildState(HNSWBuildState *state, Relation index);
// data page function
extern bool HNSWDataPageAddItem(HNSWBuildState *state, Page page,
    HNSWDataTuple *tuple);
extern HNSWDataTuple *HNSWFormDataTuple(HNSWOptions* opts,
    ItemPointer iptr, Datum *values, bool *isnull);
extern void FindItDataByOffset(Relation index, uint16 dataTupSize,
  HNSWGlobalId gid, ItemPointerData* itData); 
extern float Distance(Relation index, HNSWOptions *opts,
  const float4* vector, HNSWGlobalId gid);
// neighbor page function
extern PaseTuple* HNSWNeighborTupleFormer(void *arg); 
// hnsw build function
extern void HNSWBuildLink(Relation index, HNSWBuildState *state);
extern int GreedyUpdateNearest(Relation index, HNSWOptions *opts,
    int32 maxLevel, int level, HNSWGlobalId *nearest, float *dNearest, const float4* vector);
extern void AddLinkFromHighToLow(Relation index, HNSWBuildState *state,
    HNSWGlobalId nearest, float dNearest, int level, HNSWDataTuple* tup,
    HNSWGlobalId gid, HNSWVtable *vtable);
extern void ShrinkNbList(Relation index, HNSWBuildState *state, int level,
    PriorityQueue **linkTargets);
extern void SearchNbToAdd(Relation index, HNSWOptions* opts, int level,
    HNSWGlobalId nearest,float dNearest, PriorityQueue *results,
    HNSWVtable *vtable, HNSWDataTuple* dttup);
extern void FillNeighborPages(Relation index, PasePageList *pageList,
    PriorityQueue *resultQueue, int32 begin, int32 end);
extern void AddLink(Relation index, HNSWBuildState *state,
    HNSWGlobalId src, HNSWGlobalId dest,int level, float *qdis);

// vacuum
/*在计算机科学中，PG的vacuum是指PostgreSQL数据库中的一种自动化维护工具，
用于清理和回收数据库中的空闲空间。当数据库中的数据被删除或更新时，
空间可能会变得不连续，这可能导致性能下降。Vacuum会扫描数据库并重新组织数据，
以便更有效地使用存储空间。它还会回收已删除数据的空间，使其可供将来使用。
Vacuum是PostgreSQL数据库系统中的重要组成部分，用于维护数据库的性能和可靠性。*/
extern IndexBulkDeleteResult *
hnsw_vacuumcleanup(IndexVacuumInfo *info, IndexBulkDeleteResult *stats);

#define HNSW_METAPAGE_BLKNO 0
#define HNSW_MAGICK_NUMBER (0xDBAC0EEE)

#define HNSWPageGetMeta(_page)  ((HNSWMetaPageData *) PageGetContents(_page))

#endif  // PASE_HNSW_HNSW_H_
